package top.datacluster.basic.algorithm.leetcode.tree;

import top.datacluster.basic.algorithm.leetcode.TreeNode;

public class LeetCode1563 {

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null){
            return false;
        }
        if (A.val == B.val){
            return judge(A, B);
        }else{
            boolean label = isSubStructure(A.left, B);
            if (!label){
                return isSubStructure(A.right, B);
            }
            return label;
        }

    }

    public boolean judge(TreeNode A, TreeNode B){
        if (A == null && B == null){
            return true;
        }
        if (A != null && B == null){
            return true;
        }
        if (A == null){
            return false;
        }
        if (A.val == B.val){
            boolean equal = judge(A.left, B.left);
            if (equal){
                return judge(A.right, B.right);
            }else{
                return false;
            }
        }else{
            return false;
        }
    }



    public static void main(String[] args) {
        TreeNode node = new TreeNode(10);
        TreeNode node1 = new TreeNode(12);
        TreeNode node2 = new TreeNode(6);
        TreeNode node3 = new TreeNode(8);
        TreeNode node4 = new TreeNode(3);
        TreeNode node5 = new TreeNode(11);
        node.left = node1;
        node.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;

        TreeNode n = new TreeNode(10);
        TreeNode n1 = new TreeNode(12);
        TreeNode n2 = new TreeNode(6);
        TreeNode n3 = new TreeNode(8);

        n.left = n1;
        n.right = n2;
        n1.left = n3;
        System.out.println(new LeetCode1563().isSubStructure(node, n));

    }
}
